;;; the n-th permutation
;(defparameter n-perm 0)  ==> (0 1 2 3 4 5 6 7 8 9)
(defparameter n-perm (- (expt 10 6) 1))

(defun range (start end &optional (step 1))
  (loop for i from start to end by step collect i)) 

(defun factorial (n)
  (if (<= n 1) 1
      (* n (factorial (1- n)))))

(defun permutation-count (n)
  (factorial n))

(defun remove-n-th (n alist)
  (remove (nth n alist) alist))

;;; iteractive version
(defun p24-hack (n)
  (do ((i (1- n) (1- i))
       (seq n-perm (mod seq (permutation-count i)))
       (result '() (append result (list (nth (truncate (/ seq (permutation-count i))) perm-list))))
       (perm-list (range 0 9) (remove-n-th (truncate (/ seq (permutation-count i))) perm-list)))
      ((= seq 0) (append result perm-list))
      ))

(format t "~a~%" (time (p24-hack 10)))

;;; recursive version initialize version
"""
(defun n-th-permutation (number perm-list)
  (defun divise-num-inner (n result rest-list)
     (let* ((perm-count (permutation-count (1- (length rest-list))))
            (divisor-of-perm-count (truncate (/ n perm-count))))
       (if (= n 0) (append result rest-list)
           (divise-num-inner (mod n perm-count)
                             (append result (list (nth divisor-of-perm-count rest-list)))
                             (remove-n-th divisor-of-perm-count rest-list)))))
  (divise-num-inner number '() perm-list))
"""

;;; recursive version 
(defun n-th-permutation (n perm-list)
       (if (zerop n) perm-list
           (let* ((perm-count (permutation-count (1- (length perm-list))))
                  (divisor-of-perm-count (truncate (/ n perm-count))))
             (append (list (nth divisor-of-perm-count perm-list))
				     (n-th-permutation (mod n perm-count)
                                       (remove-n-th divisor-of-perm-count perm-list))))))

(format t "~a~%" (time (n-th-permutation n-perm (range 0 9))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;TODO 1.program to generate this sequence
;;;     2.then generate the result
;;; 362880 := (factorial 9)
;(format t "~a~%" (- (expt 10 6) (* 2 362880) (* 6 40320) (* 6 5040) (* 2 720) (* 5 120) (* 1 24) (* 2 6) (* 2 2) ))

;the 1000000th: 2783915460
;the 1000001th: 2783915604

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; code from euler forum
(defun euler24 (&optional (n 999999) (p '(0 1 2 3 4 5 6 7 8 9)))
  (permute n p))
 
(defun permute (n p)
  (let ((f (factorial (length p))))
    (cond ((= n 0) p)
          ((= n f) (reverse p))
          ((> n f) (permute (mod n (* f (1+ (length p)))) p))
          (t (multiple-value-bind (d r) (floor n (/ f (length p)))
               (cons (nth d p) (permute r (remove (nth d p) p))))))))
 
(defun factorial (n)
  (do ((i n (1- i)) (f 1 (* i f))) ((= i 0) f)))

